Non-volatile memories, such as flash memory devices, have supported the increased portability of consumer electronics, and have been utilized in relatively low power enterprise storage systems suitable for cloud computing and mass storage. The ever-present demand for almost continual advancement in these areas is often accompanied by demand to improve data storage capacity. The demand for greater storage capacity in turn stokes demand for greater storage density, so that specifications such as power consumption and form factor may be maintained and preferably reduced. As such, there is ongoing pressure to increase the storage density of non-volatile memories in order to further improve the useful attributes of such devices. However, a drawback of increasing storage density is that the stored data is increasingly prone to storage and/or reading errors.
Error control coding has been used to limit the increased likelihood of errors in memory systems. The term codeword is used herein to mean a “word” of data (for example, without limitation, 4 KB of data) that is structured according to error or erasure correcting codes. It has parity information that can be utilized to correct errors or erasures.
Error-correcting codes are adopted in numerous digital storage and communication systems. In some memory systems in which the error numbers in different codewords are unbalanced, such as due to fabrication process variations, it is more efficient to have fewer parities in each codeword and adopt global parities sharable by a group of codewords to correct extra errors. Additionally, the parities for individual codewords can be used for local failure recovery, which is essential to enable continued scaling of high-performance distributed storage. Erasures are errors whose locations are known. When the number of errors and/or erasures does not exceed the correction capability of individual codewords, they are correctable by accessing individual words instead of all the words in the group of codewords.
In integrated interleaved (II) codes, a set of linear block codewords, which are also called interleaves, are nested to create codewords of a stronger linear block code that is a subcode of the base linear block code. Hence, unlike other codes with shared parities, the integrated interleaved codes do not need another code to protect the shared parities. Using so-called generalized integrated interleaved (GII) codes, different codewords in a group of codewords can be given different correction capability.
Sharable parities are defined using parity check matrices in generalized concatenated (GC) codes. Since the encoding and decoding are both done by solving linear equations, they have higher implementation complexity than GII codes when the error correction capability is not small.
The aforementioned II and GII codes are two-layer codes. The first layer is the base code, having a certain error-correction capability, and the second layer consists of codes, which have higher error-correction capability than the first layer, generated by nesting all the codewords in a group of codewords. In systems that implement II and GII two-layer codes, if a codeword in a group has “extra” errors (i.e., more errors than the error correction capability of the first layer codes), all codewords in the group must be accessed and decoded in order to utilize the shared parity, shared by all codewords in the group, and thus the cost of correcting such extra errors is substantial, in terms of both resources used and latency incurred. Therefore new codes with encoding and decoding methods are needed to improve locality, and decrease the average cost of correcting extra errors in codewords.